A short one

Code

A short one. I won't dwell on part one, here's just the core code:

fn steps_required(steps: &str, map: &Map, start: &str, end: &str) -> usize {
    let mut location = start;
    for (i, d) in std::iter::repeat(steps.bytes()).flatten().enumerate() {
        location = map[location][usize::from(d == b'R')];
        if location.ends_with(end) {
            return i + 1;
        }
    }
    unreachable!()
}

type Map<'a> = HashMap<&'a str, [&'a str; 2]>;

Part one is just steps_required(steps, &map, "AAA", "ZZZ").

Part two reuses that core. The trick we'll be using is that we don't actually run all the ghosts in parallel. Instead, we do them one by one:

map.keys()
	.filter(|k| k.ends_with('A'))
	.map(|location| steps_required(steps, &map, location, "Z"))

This is why I do .ends_with(end) instead of == end; so I can reuse it for part 2 like this. Anyway, now we know how many steps it takes for each ghost to separately reach their own Z. If we just... assume, for no reason, that they take the exact same amount of steps to reach a Z again, we can simply calculate the least common multiple of all of those to get the result:

	.reduce(lcm)

The funniest part was my coworker asking me how many digits my solution had, because he at first implemented it directly (iterating all ghosts simultaneously until they're all at a Z). I started counting out loud "1... 2... .... 14.", at which point he dejectedly said "Alright, time to stop that process then."

As for the assumption: The problem just looked like it calls for this lcm-based solution. So I tried it, and it worked. But there's nothing in the puzzle that says that these step counts are actually cycles; because the lcm approach only works if they're cycles. The whole idea is that cycles of different lengths overlap at their least common multiple: If you had two things that happen every 6 and 8 seconds respectively, at second lcm(6, 8) = 24 they'd happen simultaneously.

I'm sure if I played around more with the data set I'd see that cycle pattern, but as-is, my intuition shortcut me to the correct solution directly. I'll take it.